package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 1594. 矩阵的最大非负积
 *
 * @author liw
 * @version 1.0
 * @date 2022/1/10 21:36
 */
public class MaxProductPath {


    public static void main(String[] args) {
        MaxProductPath test = new MaxProductPath();


        // 2
        int[][] arr = {{1, 4, 4, 0}, {-2, 0, 0, 1}, {1, -1, 1, 1}};

        // 8
//        int[][] arr = {{1, -2, 1}, {1, -2, 1}, {3, -4, 1}};

        // 0
//        int[][] arr = {{1, 3}, {0, -4}};

        // -1
//        int[][] arr = {{-1, -2, -3}, {-2, -3, -3}, {-3, -3, -2}};

        int i = test.maxProductPath(arr);

        System.out.println(i);
    }


    public int maxProductPath(int[][] grid) {
        int a = grid.length;
        int b = grid[0].length;
        long[][][] arr = new long[a][b][2];
        boolean flag = false;
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                int v = grid[i][j];
                if (v == 0) {
                    flag = true;
                }
                if (i == 0) {
                    if (j == 0) {
                        if (v > 0) {
                            arr[i][j][0] = v;
                            arr[i][j][1] = 0;
                        } else {
                            arr[i][j][0] = 0;
                            arr[i][j][1] = v;
                        }
                    } else {
                        long[] ints = arr[i][j - 1];
                        long max = ints[0];
                        long min = ints[1];
                        if (v > 0) {
                            arr[i][j][0] = v * max ;
                            arr[i][j][1] = v * min;
                        } else {
                            arr[i][j][0] = v * min;
                            arr[i][j][1] = v * max;
                        }
                    }
                } else if (j == 0) {
                    long[] ints = arr[i - 1][j];
                    long max = ints[0];
                    long min = ints[1];
                    if (v > 0) {
                        arr[i][j][0] = v * max;
                        arr[i][j][1] = v * min;
                    } else {
                        arr[i][j][0] = v * min;
                        arr[i][j][1] = v * max;
                    }
                } else {
                    long[] ints1 = arr[i][j - 1];
                    long max1 = ints1[0];
                    long min1 = ints1[1];
                    long[] ints2 = arr[i - 1][j];
                    long max2 = ints2[0];
                    long min2 = ints2[1];
                    if (v > 0) {
                        arr[i][j][0] = v * Math.max(max1, max2);
                        arr[i][j][1] = v * Math.min(min1, min2);
                    } else {
                        arr[i][j][0] = v * Math.min(min1, min2);
                        arr[i][j][1] = v * Math.max(max1, max2);
                    }
                }
            }
        }
        long i = arr[a - 1][b - 1][0];
        if (i > 0) {
            return (int)( i% 1000000007);
        }
        if (flag) {
            return 0;
        }
        return -1;
    }

}
